// 矩阵乘法
// 矩阵快速幂
// 矩阵快速幂解决斐波那契第n项的问题

#include <bits/stdc++.h>

using namespace std;

// 矩阵相乘
// a的列数一定要等于b的行数
vector<vector<int>> multiply(const vector<vector<int>>& a, const vector<vector<int>>& b) 
{
    int n = a.size();
    int m = b[0].size();
    int k = a[0].size();
    vector<vector<int>> ans(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < m; j++) 
        {
            for (int c = 0; c < k; c++) 
            {
                ans[i][j] += a[i][c] * b[c][j];
            }
        }
    }
    return ans;
}

// 矩阵快速幂
// 要求矩阵m是正方形矩阵
vector<vector<int>> power(vector<vector<int>> m, int p) 
{
    int n = m.size();
    // 对角线全是1、剩下数字都是0的正方形矩阵，称为单位矩阵
    // 相当于正方形矩阵中的1，矩阵a * 单位矩阵 = 矩阵a
    vector<vector<int>> ans(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) 
    {
        ans[i][i] = 1;
    }
    for (; p != 0; p >>= 1) 
    {
        if ((p & 1) != 0) 
        {
            ans = multiply(ans, m);
        }
        m = multiply(m, m);
    }
    return ans;
}

// 打印二维矩阵
void print(const vector<vector<int>>& m) 
{
    for (int i = 0; i < m.size(); i++) 
    {
        for (int j = 0; j < m[0].size(); j++) 
        {
            if (m[i][j] < 10)
                cout << m[i][j] << "   ";
            else if (m[i][j] < 100) 
                cout << m[i][j] << "  ";
            else
                cout << m[i][j] << " ";
        }
        cout << endl;
    }
}

// 矩阵乘法的展示
void f1() 
{
    vector<vector<int>> a = { { 1, 3 }, { 4, 2 } };
    vector<vector<int>> b = { { 2, 3 }, { 3, 2 } };
    //        2  3
    //        3  2
    //
    // 1  3  11  9
    // 4  2  14 16
    vector<vector<int>> ans1 = multiply(a, b);
    print(ans1);
    cout << "======" << endl;
    vector<vector<int>> c = { { 2, 4 }, { 3, 2 } };
    vector<vector<int>> d = { { 2, 3, 2 }, { 3, 2, 3 } };
    //         2  3  2
    //         3  2  3
    //
    // 2  4   16 14 16
    // 3  2   12 13 12
    vector<vector<int>> ans2 = multiply(c, d);
    print(ans2);
    cout << "======" << endl;
    vector<vector<int>> e = { { 2, 4 }, { 1, 2 }, { 3, 1 } };
    vector<vector<int>> f = { { 2, 3 }, { 4, 1 } };
    //          2  3
    //          4  1
    //
    // 2  4    20 10
    // 1  2    10  5
    // 3  1    10 10
    vector<vector<int>> ans3 = multiply(e, f);
    print(ans3);
    cout << "======" << endl;
    vector<vector<int>> g = { { 3, 1, 2 } };
    vector<vector<int>> h = { { 1, 2, 1 }, { 3, 2, 1 }, { 4, 2, -2 } };
    //           1  2  1
    //           3  2  1
    //           4  2 -2
    //
    // 3  1  2  14 12  0
    vector<vector<int>> ans4 = multiply(g, h);
    print(ans4);
}

// 矩阵快速幂用法的展示
void f2() 
{
    // 只有正方形矩阵可以求幂
    vector<vector<int>> a = { { 1, 2 }, { 3, 4 } };
    // 连乘得到矩阵a的5次方
    vector<vector<int>> b = multiply(a, multiply(a, multiply(a, multiply(a, a))));
    print(b);
    cout << "======" << endl;
    // 矩阵快速幂得到矩阵a的5次方
    print(power(a, 5));
}

// 用矩阵乘法解决斐波那契第n项的问题
void f3() 
{
    // 0  1  1  2  3  5  8 13 21 34...
    // 0  1  2  3  4  5  6  7  8  9
    vector<vector<int>> start = { { 1, 0 } };
    vector<vector<int>> m = { { 1, 1 }, { 1, 0 } };
    vector<vector<int>> a = multiply(start, m);
    print(a);
    cout << "======" << endl;
    vector<vector<int>> b = multiply(a, m);
    print(b);
    cout << "======" << endl;
    vector<vector<int>> c = multiply(b, m);
    print(c);
    cout << "======" << endl;
    vector<vector<int>> d = multiply(c, m);
    print(d);
}

// 用矩阵快速幂解决斐波那契第n项的问题
void f4() 
{
    // 0  1  1  2  3  5  8 13 21 34...
    // 0  1  2  3  4  5  6  7  8  9
    vector<vector<int>> start = { { 1, 0 } };
    vector<vector<int>> m = { { 1, 1 }, { 1, 0 } };
    vector<vector<int>> a = multiply(start, power(m, 1));
    print(a);
    cout << "======" << endl;
    vector<vector<int>> b = multiply(start, power(m, 2));
    print(b);
    cout << "======" << endl;
    vector<vector<int>> c = multiply(start, power(m, 3));
    print(c);
    cout << "======" << endl;
    vector<vector<int>> d = multiply(start, power(m, 4));
    print(d);
}

int main() 
{
    cout << "f1() : " << endl;
    cout << "矩阵乘法展示开始" << endl;
    f1();
    cout << "矩阵乘法展示结束" << endl;
    cout << endl;

    cout << "f2() : " << endl;
    cout << "矩阵快速幂展示开始" << endl;
    f2();
    cout << "矩阵快速幂展示结束" << endl;
    cout << endl;

    cout << "f3() : " << endl;
    cout << "求斐波那契数列第n项" << endl;
    cout << "用矩阵乘法解决" << endl;
    cout << "展示开始" << endl;
    f3();
    cout << "展示结束" << endl;
    cout << endl;

    cout << "f4() : " << endl;
    cout << "求斐波那契数列第n项" << endl;
    cout << "用矩阵快速幂解决" << endl;
    cout << "展示开始" << endl;
    f4();
    cout << "展示结束" << endl;
    cout << endl;

    return 0;
}